package fibonacci

import (
	"math"
)

//   1 1 2 3 5 8 ......

// Iterate 迭代法
func Iterate(n int64) (int64, int) {
	array := []int64{0, 1, 1}
	count := 0
	if n <= 2 {
		return array[n], 0
	}
	for i := int64(3); i <= n; i++ {
		count++
		array = append(array, array[i-1]+array[i-2])
	}
	return array[n], count
}

// Iterate2 迭代法
func Iterate2() int32 {
	array := []int32{0, 1, 1}

	for i := int32(3); i < math.MaxInt8; i++ {
		array = append(array, array[i-1]+array[i-2])
		if array[i-1] > array[i] {
			return i - 1
		}
	}
	return -1
}

// Iterate3 迭代法
func Iterate3(n int64) float64 {
	array := []float64{0, 1, 1}
	if n <= 2 {
		return array[n]
	}
	for i := int64(3); i <= n; i++ {
		array = append(array, array[i-1]+array[i-2])
	}
	return array[n]
}

// ImprovedIterative 迭代改进法
func ImprovedIterative(n int64) (ans int64, count int64) {
	a := int64(1)
	b := int64(1)
	count = 0
	for i := int64(3); i <= n; i++ {
		count++
		ans = a + b
		a = b
		b = ans
	}
	return ans, count
}

var count4 = 0

// Recursion 递归法
func Recursion(n int64) (ans int64) {
	if n <= 2 {
		return 1
	}
	count4++
	return Recursion(n-1) + Recursion(n-2)
}

// Recursion2 递归法2
func Recursion2(n int32) (ans int32) {
	if n <= 2 {
		return 1
	}
	return Recursion2(n-1) + Recursion2(n-2)
}

// Formula 公式法
func Formula(n int64) float64 {
	ans := (math.Pow((math.Sqrt(5.0)+1.0)/2.0, float64(n)) - math.Pow((1.0-math.Sqrt(5.0))/2.0, float64(n))) * (1.0 / math.Sqrt(5.0))
	return ans
}

type matrix [2][2]int

func multiply(a, b matrix) (c matrix) {
	for i := 0; i < 2; i++ {
		for j := 0; j < 2; j++ {
			c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j]
		}
	}
	return
}

var count5 = 0

func quickPow(a matrix, n int) matrix {
	ret := matrix{{1, 0}, {0, 1}}
	for ; n > 0; n >>= 1 {
		count5++
		if n&1 == 1 {
			ret = multiply(ret, a)
		}
		a = multiply(a, a)
	}
	return ret
}

// Matrix 矩阵法
func Matrix(n int) int {
	if n < 2 {
		return n
	}
	res := quickPow(matrix{{1, 1}, {1, 0}}, n-1)
	return res[0][0]
}
